1. Field of the Invention
The present invention generally relates to a method and related apparatus for managing an address table and, more particularly, to a method for managing a medium access control address table and related media access control chip.
2. The Related Art
An Ethernet switch provides a plurality of ports for network connection. Each port can provide a full-duplex transmission at the line speed 10M/100M/1000M. The core of an Ethernet switch is a medium access controller (MAC controller), which is typically responsible for the second and part of the third layer and above operation. The MAC controller is coupled with a physical layer (PHY) for providing a plurality of ports for network connection to transmit and receive signals with a remote host. The MAC controller temporarily stores received packets from all the ports, and transfer them to the destination port. The MAC controller usually uses external memory chip or built-in memory for temporary storage of the packets, such as the built-in 1 Mbits (=128 Kbytes) RAM. As an Ethernet switch includes 8, 16 or 24 ports, the limited memory space must be efficiently utilized in order to provide these ports for temporary storage and transferring of packets.
The packets received by an Ethernet switch can be categorized as uni-cast packets, multi-cast packets, and broadcast packets. A unit-cast packet is received by a port of the Ethernet switch and transmitted from another port. A multi-cast packet is received by a port of the Ethernet switch and transmitted from a plurality of other ports. A broadcast packet is received by a port of the Ethernet switch and transmitted from all the other ports. In general, the maximum length of an Ethernet packet is 1522 bytes, and in NAS/SAN system, a jumbo packet can be as long as 9.6K bytes. The MAC controller uses external or built-in memory for temporary storage of packets, and the MAC controller must configure the external or built-in memory to establish an appropriate data structure and format in the initialization stage for later operation.
FIG. 1 of the attached drawings shows the structure of an Ethernet packet, which is designated with reference numeral 100. The Ethernet packet 100 includes a destination medium access control (DMAC) address 110, a source medium access control (SMAC) address 120, a payload 130, and a cyclic redundant code (CRC) 140. The Ethernet switch configures an address table in the built-in 128 Kbytes static RAM for recording the association between MAC address and ports, so that the switch can look up the table and quickly find the destination port for the received Ethernet packet 100. The majority of the static RAM is for buffering the packets received by all the ports. Each packet, after entering the switch, uses SMAC address 120 and its source port to appropriately record the information in the address table (called learning process) for later inquiry. On the other hand, The Ethernet switch will use DMAC address 110 for table look-up. If corresponding information is found, the associated port mask can be known. Otherwise, a broadcast will be performed.
FIG. 2 shows a schematic view of a dual-slot address table. The conventional dual-slot address access techniques, for example, configures address table 200 as 2K buckets, with each bucket having two slots. A bucket address can be used to find a specific bucket. Bucket 210 has a slot 210A and a slot 210B, and bucket 220 has a slot 220A and a slot 220B. That is, each of the 2K buckets has an A slot and a B slot. Each slot is for displaying the related information of MAC address. Each MAC address is 48-bit long, expressed as MAC[47:0]. Therefore, related information on at most 4K MAC addresses can be recorded. A direct map or hash method can be used to map an MAC address to a specific bucket address and slot. Typically, in the MAC address learning stage, each MAC address uses CRC-11 polynomial hashing computation to obtain the 11-bit bucket address Hash[10:0]. For example, when mapped to bucket 250, slot 250A is given the first priority to store the MAC address. If slot 250A has already stored another MAC address, slot 250B is used to store the 37 bits (i.e., MAC[47:11]) and related information of that MAC address. If the direct map method is used, MAC[10:0] is used as bucket address, and the 37 bits (i.e., MAC[47:11]) and related information of that MAC address are stored into the appropriate slot. The advantage of using a hash mapping method is to increase the randomness of the MAC address to prevent the neighboring MAC addresses from using the A or B slot of the same bucket and increase the opportunity of broadcasting.
When inquiring the DMAC address of a packet, the DMAC address is used in CRC-11 polynomial hashing computation to obtain the 11-bit bucket address Hash[10:0]. For example, if bucket 250 is mapped to, slot 250A is first compared for match. If MAC[47:11] in slot 250A matches DMAC[47;11] of the packet, the related information is available. If 250A does not match, slot 250B is compared against the DMAC of the packet. When both slots do not match, the packet is broadcasted.
Using a small part of the limited static RAM for address look-up table, the address table can only hold a small number of entries. The efficient use of the limit-sized address table is related to the switching efficiency of the Ethernet switch, and it is important to the forwarding control unit to find a solution.